#include <algorithm>
#include <iostream>
#include <memory>
#include <stack>
#include <string>
#include <vector>

using std::string;

struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};

class CodecDfs {
public:
    string serialize(TreeNode *root) {
        std::string values;
        serialize(root, values);
        return values;
    }

    void serialize(TreeNode *root, std::string &values) {
        if (root) {
            values += std::to_string(root->val);
            if (root->left or root->right) {
                values += "{";
                if (root->left) {
                    serialize(root->left, values);
                }
                if (root->right) {
                    values += ",";
                    serialize(root->right, values);
                }
                values += "}";
            }
        }
    }

    TreeNode *deserialize(string data) {
        if (data == "")
            return nullptr;
        TreeNode *root = new TreeNode(0);
        int index = 0;
        deserialize(data, index, root);
        return root;
    }

    bool is_digtal(char c) { return c == '-' or (c >= '0' and c <= '9'); }

    int get_int(const std::string &data, int &index) {
        std::string num_str;
        while (is_digtal(data[index])) {
            num_str += data[index];
            ++index;
        }
        return std::stoi(num_str);
    }

    void deserialize(const std::string &data, int &index, TreeNode *cur) {
        int num = get_int(data, index);
        cur->val = num;
        if (data[index] == '{') {
            ++index;
            if (is_digtal(data[index])) {
                cur->left = new TreeNode(0);
                deserialize(data, index, cur->left);
            }
            if (data[index] == ',') {
                ++index;
                cur->right = new TreeNode(0);
                deserialize(data, index, cur->right);
            }
            if (data[index] == '}')
                ++index;
        }
    }
};

auto split(const std::string &str, char limiter) {
    std::vector<std::string> ss{""};
    for (auto c : str) {
        if (c == limiter) {
            ss.push_back("");
        } else {
            ss.back().push_back(c);
        }
    }
    return ss;
}

class Codec {
public:
    // Encodes a tree to a single string.
    // BFS
    string serialize(TreeNode *root) {
        std::string values;
        auto cur_level_nodes = std::make_unique<std::vector<TreeNode *>>();
        cur_level_nodes->push_back(root);
        int count_ptr = 0;

        if (root) {
            ++count_ptr;
        } else {
            return "";
        }
        while (count_ptr != 0) {
            auto next_level_nodes = std::make_unique<std::vector<TreeNode *>>();
            count_ptr = 0;
            for (auto node : (*cur_level_nodes)) {
                if (node == nullptr) {
                    values += "n,";
                    next_level_nodes->push_back(nullptr);
                    next_level_nodes->push_back(nullptr);
                } else {
                    if (node->left)
                        ++count_ptr;
                    if (node->right)
                        ++count_ptr;
                    next_level_nodes->push_back(node->left);
                    next_level_nodes->push_back(node->right);
                    values += std::to_string(node->val) + ",";
                }
            }
            cur_level_nodes = std::move(next_level_nodes);
        }
        values.pop_back();
        return values;
    }

    // Decodes your encoded data to tree.
    TreeNode *deserialize(string data) {
        if (data == "")
            return nullptr;
        auto ss = split(data, ',');
        std::vector<TreeNode *> node_ptrs;
        for (auto s : ss) {
            if (s == "n")
                node_ptrs.push_back(nullptr);
            else
                node_ptrs.push_back(new TreeNode(std::stoi(s)));
        }
        for (int i = 0; i < ss.size() / 2; ++i) {
            if (node_ptrs[i] == nullptr)
                continue;
            node_ptrs[i]->left = node_ptrs[i * 2 + 1];
            if (node_ptrs.size() > i * 2 + 2)
                node_ptrs[i]->right = node_ptrs[i * 2 + 2];
        }
        return node_ptrs.front();
    }
};

void print(TreeNode *root) {
    if (root) {
        std::cout << root->val << ", ";
        print(root->left);
        print(root->right);
    }
}

int main() {
    Codec codec;
    CodecDfs codec_dfs;

    // auto root = codec.deserialize("-1,0,1");
    // auto root = codec.deserialize("");
    auto data_dfs = "1{2{-3},5{1,2}}";
    auto root_dfs = codec_dfs.deserialize(data_dfs);
    auto root = new TreeNode(1);
    std::cout << codec_dfs.serialize(root) << '\n';
    // std::cout << data_dfs << '\n';
    std::cout << codec.serialize(root_dfs) << '\n';
    std::cout << codec_dfs.serialize(root_dfs) << '\n';
    // std::cout << codec.serialize(root) << '\n';
    return 0;
}
